/*
 * @lc app=leetcode.cn id=68 lang=cpp
 *
 * [68] 文本左右对齐
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<string> fullJustify(vector<string> &words, int maxWidth)
    {
        vector<string> ans;
        string s;
        for (int i = 0, j = 0; i < words.size(); i = j)
        {
            s = words[j++];
            int len = s.length();
            while (j < words.size() && len + 1 + words[j].length() <= maxWidth)
            {
                len += 1 + words[j].length();
                j++;
            }
            if(j == words.size())
            {
                //当前行是最后一行
                for(++i; i < j; i++)
                {
                    s += " " + words[i];
                }
                while (s.length() < maxWidth)
                {
                    s += " ";
                }
                
            }
            else
            {
                int num_words = j - i;
                if (num_words == 1)
                {
                    int len = s.length();
                    for (int k = 0; k < maxWidth - len; k++)
                    {
                        s += " ";
                    }
                }
                else
                {
                    int num_spaces = (maxWidth - len) / (num_words - 1) + 1; // num_words - 1个位置需要插入空格
                    // +1 是因为 len 里面加上了空格的个数，多减了一部分

                    int left = (maxWidth - len) % (num_words - 1);

                    vector<int> num_spaces_vec;
                    for (int k = 0; k < num_words - 1; k++)
                    {
                        if (left)
                        {
                            num_spaces_vec.push_back(num_spaces + 1);
                            left--;
                        }
                        else
                            num_spaces_vec.push_back(num_spaces);
                    }
                    for (int k = 0; k < num_words - 1; k++)
                    {
                        // cout << s << " ";
                        // cout << num_spaces_vec[k] << " ";
                        for (int num_space = 0; num_space < num_spaces_vec[k]; num_space++)
                        {
                            s += " ";
                        }
                        s += words[i + k + 1];
                        // cout << s << " ";

                    }
                    // cout << endl;
                }
            }

            {
                ans.push_back(s);
                s = "";
            }
        }
        if (s.length())
            ans.push_back(s);

        return ans;
    }
};
// @lc code=end
